---
title: "乘积最大"
created: 2025-11-28
tags:
  - 算法
---

# 乘积最大

## 题目 [乘积最大](https://www.acwing.com/problem/content/1241/)

![[image-3cfcc623.png]]

## 思路分析

![[image-fc53fb5b.png]]

如果 k == n ,那么就证明所有的数字是全部都选,

如果 k < n , 那么就要思考怎样去选择了:

      k 如果是偶数的话,选出来的结果一定是非负数 , 原因如下:

            负数的个数是偶数个的话,负负得正,那么一定是非负数

            负数的个数如果是奇数个的话,那么我们就只选偶数个绝对值最大的负数

      k 如果是奇数个的话,

            所有的数字如果都是负数,那么选出来的结果也一定都是负数

            否则的话,则一定至少有 1个非负数, 那么我们将最大的数取出来,
此时要选的个数就是 k--,

            k-- 是偶数,那么就又转化为 k-- 是偶数的情况思考

     这里可以巧妙一下 k是奇数的情况 先把最大的数取出来 如果是小于0就说明全小于0 最后答案一定为
     负 如果大于0 就变成前面一样情况处理

从左右分别往里逼近去选 类似于归并排序 把左边当成一个集合 右边当成一个集合 左边的俩是左边乘积最大的 右边的俩是右边乘积最大的 他们之间做双指针
就可以取出乘积全局最大的俩

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N=100010,mod=1000000009;

int a[N];

int n,k;

int main()

{

    cin>>n>>k;

    for(int i=0;i<n;i++)

        cin>>a[i];

    sort(a,a+n);

    LL res=1;

    int l=0,r=n-1;

    int sign=1;//符号 一开始令为正

    if(k&1){

        res=a[r];//奇数时 把最大的先取出来 问题转变成偶数情况

        r--;

        k--;

        if(res<0)

            sign=-1;//若最大的都是负 说明全是负数 最后答案一定是负的（奇数个且全负）

    }

    while(k){

        LL x=(LL)a[l]*a[l+1],y=(LL)a[r]*a[r-1];

        if(x*sign>y*sign){

            res=x%mod*res%mod;

            //不可以写成(x*res)%mod ,也不可以写成res%mod*x%mod

            //x最大是10^10，如果不先取模的话，和res相乘的结果最大是10^19,会爆long long

            l+=2;

        }

        else{

            res=y%mod*res%mod;

            r-=2;

        }

        k-=2;

    }

    cout<<res;

    return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[三国游戏|三国游戏]] 🏠 [[00-刷题理模型]] ➡️ [[排序 权贪心（短作业优先 重权值优先）|排序 权贪心（短作业优先 重权值优先）]]